package com.example.leetcode.c1_c100.c22;
/**
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 *
 *  
 *
 * 示例：
 *
 * 输入：n = 3
 * 输出：[
 *        "((()))",
 *        "(()())",
 *        "(())()",
 *        "()(())",
 *        "()()()"
 *      ]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/generate-parentheses
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

import java.util.LinkedList;
import java.util.List;

/**
 * 括号生成
 * @author zhanpengguo
 * @date 2020-09-10 8:06
 */
public class Solution {

    List<String> res = new LinkedList<>();
    int max;
    int n;

    public List<String> generateParenthesis(int n) {
        // 当左括号小于n时，可以放置左括号
        // 当右括号小于左括号，可以放置右括号
        this.max = 2 * n;
        this.n = n;
        backtrack(new StringBuffer(), 0, 0);
        return res;
    }

    private void backtrack(StringBuffer sb, int left, int right) {
        if (sb.length() == max) {
            res.add(sb.toString());
            return;
        }
        if (left < n) {
            sb.append('(');
            backtrack(sb, left + 1, right);
            sb.deleteCharAt(sb.length() - 1);
        }
        if (right < left) {
            sb.append(')');
            backtrack(sb, left, right + 1);
            sb.deleteCharAt(sb.length() - 1);
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        List<String> strings = solution.generateParenthesis(3);
        strings.forEach(System.out::println);
    }
}
